package de.hwr.sudokuspielehr.generator;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import de.hwr.sudokuspielehr.data.Sudoku;

/**
 * 
 * @author J. Reischauer
 * 
 */
public final class SudokuGenerator {
	public static final int DIFFICULTY_VERYEASY = 1;
	public static final int DIFFICULTY_EASY = 2;
	public static final int DIFFICULTY_ADVANCED = 3;
	public static final int DIFFICULTY_IMPOSSIBLE = 4;

	public static int determineDifficulty(Sudoku pSudoku) {
		Sudoku s = pSudoku.clone();
		s.scan();

		if (s.getNextEmptyCellIndex(0) == -1) {
			int numberOfEmptyCells = 0;
			for (int n : s.getInitialBoard()) {
				if (n == Sudoku.EMPTY_CELL_VALUE) {
					numberOfEmptyCells++;
				}
			}

			if (numberOfEmptyCells < 51) {
				return DIFFICULTY_VERYEASY;
			} else {
				return DIFFICULTY_EASY;
			}
		} else {
			s.solve();

			if (s.getNextEmptyCellIndex(0) == -1) {
				return DIFFICULTY_ADVANCED;
			} else {
				return DIFFICULTY_IMPOSSIBLE;
			}
		}
	}

	public static Sudoku generateEasySudoku() {
		Sudoku s = generateEasySudokuA(51);
		s.setDifficulty("Leicht");
		return s;
	}

	public static Sudoku generateVeryEasySudoku() {
		Sudoku s = generateEasySudokuA(46);
		s.setDifficulty("Sehr leicht");
		return s;
	}

	public static Sudoku generateAdvancedSudoku() {
		Sudoku s = generateSudoku(8, 55);
		s.setDifficulty("Fortgeschritten");
		return s;
	}

	private static Sudoku generateEasySudokuA(int pAmount) {
		Sudoku s = generateSudoku(9, 0);
		Random r = new Random();
		int i = pAmount;
		List<Integer> cellsToRemove = new ArrayList<Integer>();

		while (i > 0) {
			int currentIndex = r.nextInt(81);

			if (!cellsToRemove.contains(currentIndex)) {
				int oldValue = s.getCell(currentIndex);
				for (int n : cellsToRemove) {
					s.setCell(n, Sudoku.EMPTY_CELL_VALUE);
				}
				s.setCell(currentIndex, Sudoku.EMPTY_CELL_VALUE);
				s.scan();

				if (s.isFilled()) {
					cellsToRemove.add(currentIndex);
					i--;
				} else {
					s.setCell(currentIndex, oldValue);
				}
			}
		}

		for (int index : cellsToRemove) {
			s.setCell(index, Sudoku.EMPTY_CELL_VALUE);
		}

		s.setInitialBoard(s.getBoard());
		Sudoku solvedSudoku = s.clone();
		solvedSudoku.solve();
		s.setSolvedBoard(solvedSudoku.getBoard());

		return s;
	}

	/**
	 * Generates a Sudoku.
	 * 
	 * @param pFillAmount
	 *            amount of numbers randomly filled into the initial empty
	 *            Sudoku.
	 * @param pRemoveAmount
	 *            amount of numbers randomly removed from the solved sudoku
	 * @return the resulting sudoku
	 */
	@SuppressWarnings("deprecation")
	public static Sudoku generateSudoku(int pFillAmount, int pRemoveAmount) {
		int amount = 5;
		List<GenerationThread> threads = new ArrayList<GenerationThread>();
		GenerationThread winningThread = null;

		for (int i = 0; i < amount; i++) {
			GenerationThread g = new GenerationThread(pFillAmount, pRemoveAmount);
			g.start();
			threads.add(g);
		}

		boolean finished = false;

		while (!finished) {
			for (GenerationThread g : threads) {
				if (g.hasFinished()) {
					winningThread = g;
					finished = true;
					break;
				}
			}
		}

		for (GenerationThread g : threads) {
			if (g.isAlive()) {
				g.stop();
			}
		}

		Sudoku sudoku = winningThread.getResult();
		sudoku.setInitialBoard(sudoku.getBoard());
		Sudoku solvedSudoku = sudoku.clone();
		solvedSudoku.solve();
		sudoku.setSolvedBoard(solvedSudoku.getBoard());
		sudoku.setCreationInfo("Computer");
		return sudoku;
	}

	/**
	 * Generates a Sudoku with given fill- and remove amount.
	 * 
	 * @param pFillAmount
	 *            amount of numbers randomly filled into the initially empty
	 *            Sudoku
	 * @param pRemoveAmount
	 *            amount of numbers randomly removed from the solved Sudoku
	 * @return the resulting Sudoku
	 */
	public static Sudoku generateSudokuA(int pFillAmount, int pRemoveAmount) {
		Sudoku sudoku = new Sudoku();
		Random rng = new Random();

		List<Integer> alreadyFilledCells = new ArrayList<Integer>();
		for (int i = 0; i < pFillAmount; i++) {
			int currentIndex;
			do {
				currentIndex = rng.nextInt(81);
			} while (alreadyFilledCells.contains(currentIndex));

			alreadyFilledCells.add(currentIndex);

			int currentValue;
			do {
				currentValue = rng.nextInt(9) + 1;
				sudoku.setCell(currentIndex, currentValue);
			} while (sudoku.containsErrors());
		}

		sudoku.solve();

		List<Integer> alreadyRemovedCells = new ArrayList<Integer>();
		for (int i = 0; i < pRemoveAmount; i++) {
			int currentIndex;
			do {
				currentIndex = rng.nextInt(81);
			} while (alreadyRemovedCells.contains(currentIndex));

			alreadyRemovedCells.add(currentIndex);
			sudoku.setCell(currentIndex, Sudoku.EMPTY_CELL_VALUE);
		}

		return sudoku;
	}

}

/**
 * 
 * @author J. Reischauer
 * 
 */
class GenerationThread extends Thread {

	/**
	 * Sudoku instance to work with in this Thread.
	 */
	private Sudoku sudoku = null;

	/**
	 * Flag.
	 */
	private boolean finished = false;

	/**
	 * Amount of numbers to fill into the initially empty Sudoku.
	 */
	private int fillAmount;

	/**
	 * Amount of numbers to remove from the solved Sudoku.
	 */
	private int removeAmount;

	/**
	 * Constructor of GenerationThread.
	 * 
	 * @param pFillAmount
	 *            Amount of numbers to fill into the initially empty Sudoku
	 * @param pRemoveAmount
	 *            Amount of numbers to remove from the solved Sudoku
	 */
	public GenerationThread(int pFillAmount, int pRemoveAmount) {
		fillAmount = pFillAmount;
		removeAmount = pRemoveAmount;
	}

	@Override
	public void run() {
		sudoku = SudokuGenerator.generateSudokuA(fillAmount, removeAmount);
		finished = true;
	}

	/**
	 * Finished?
	 * 
	 * @return true, false
	 */
	public boolean hasFinished() {
		return finished;
	}

	/**
	 * Returns the resulting Sudoku.
	 * 
	 * @return resulting sudoku
	 */
	public Sudoku getResult() {
		return sudoku;
	}
}
